#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

//有两种方法解决
//时间复杂度为O(n^2)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);//以nums中的i结尾的最长子序列长度
        for(int i = 1;i<nums.size();++i){
            for(int j = 0;j<i;++j){
                if(nums[i]>nums[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};


//利用二分法求解
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //怎么找到最长的子序列，答，贪心策略：每次上升子序列最后加上的那个数尽可能的小
        vector<int> dp;//dp[i]为长度为i+1时末尾最小的数
        for(int i = 0;i<nums.size();++i){
            if(i==0){
                dp.push_back(nums[i]);
            }
            else{
                if(nums[i]>dp.back()){
                    dp.push_back(nums[i]);
                }
                else{
                    auto it = lower_bound(dp.begin(),dp.end(),nums[i]);
                    *it = nums[i];
                }
            }
        }
        return dp.size();
    }
};